//
// Created by 田建昆 on 2020/12/11.
//

#include "sort.h"

static int partition(int arr[], int lo, int hi)
{
    int i = lo, j = hi+1;
    int v = arr[lo];
    while (1) {
        while (arr[++i] < v) if (i == hi) break;
        while (arr[--j] > v) if (j == lo) break;

        if (i >= j) break;
        swap(arr[i], arr[j]);
    }
    swap(arr[lo], arr[j]);
    return j;
}

static void sort(int arr[], int lo, int hi)
{
    if (lo >= hi) return;
    int j = partition(arr, lo, hi);
    sort(arr, lo, j-1);
    sort(arr, j+1, hi);
}

void quick(int arr[], int size)
{
    sort(arr, 0, size-1);
}